# 快速排序归并方法
import random


def partition(ls, left, right):
    temp = ls[left]
    # 如果左下标和右下标不相等则继续归并
    while left < right:
        # 先从右侧进行检索，找到小于基准值的值放入左侧
        while left < right and ls[right] >= temp:
            right = right - 1
        ls[left] = ls[right]
        # print(ls, '左侧')
        # 再从左侧进行检索找到大于基准值的值放入刚刚右侧的空位
        while left < right and ls[left] <= temp:
            left = left + 1
        ls[right] = ls[left]
        # print(ls, '右侧')
    # 当左下标和右下标一致的时候说明已经归并完成此时将最开始保存的temp值放入该下标中
    ls[left] = temp
    # 返回归并的下标
    return left


def quick_sort(ls, left, right):
    # 至少2个元素
    if left < right:
        mid = partition(ls, left, right)
        quick_sort(ls, left, mid - 1)
        quick_sort(ls, mid + 1, right)
    print(ls)


# ls = [5, 7, 4, 6, 3, 1, 2, 9, 8]
# print(ls)
# partition(ls, 0, len(ls) - 1)
# print(ls)
ls = []
for x in range(10):
    ls.append(random.randint(1, 1000))
quick_sort(ls, 0, len(ls) - 1)
